package com.sukaiyi.leetcode._365water_and_jug_problem;

import org.junit.jupiter.api.Test;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertTrue;

/**
 * @author sukaiyi
 * @date 2020/05/14
 * @see <a href="https://leetcode-cn.com/problems/water-and-jug-problem/">题目地址</a>
 */
public class Solution {

    @Test
    public void test() {
        assertTrue(canMeasureWater(104597, 104623, 123));
        assertTrue(canMeasureWater(1, 2, 3));
        assertTrue(canMeasureWater(3, 5, 4));
        assertFalse(canMeasureWater(2, 6, 5));
    }

    public boolean canMeasureWater(int x, int y, int z) {
        if (z == 0) {
            return true;
        }
        Set<String> visited = new HashSet<>();
        Queue<int[]> queue = new LinkedList<>();
        visited.add("0-0");
        queue.offer(new int[]{0, 0});
        while (!queue.isEmpty()) {
            int[] state = queue.poll();
            if (state[0] == z || state[1] == z || state[0] + state[1] == z) {
                return true;
            }
            // 当前状态可以转移到哪些状态
            int[][] ns = new int[][]{
                    new int[]{x, state[1]},
                    new int[]{state[0], y},
                    new int[]{0, state[1]},
                    new int[]{state[0], 0},
                    new int[]{Math.min(state[0] + state[1], x), Math.max(state[1] - x + state[0], 0)},
                    new int[]{Math.max(state[0] - y + state[1], 0), Math.min(state[1] + state[0], y)}
            };
            for (int i = 0; i < ns.length; i++) {
                int[] ni = ns[i];
                String mark = ni[0] + "-" + ni[1];
                if (!visited.contains(mark)) {
                    queue.offer(ni);
                    visited.add(mark);
                }
            }
        }
        return false;
    }
}
